package LCR;

public class isPalindrome3 {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = middleNode(head);
        ListNode pre = mid;
        mid = reverseList(mid);
        while(mid != null && head != null) {
            if(head.val != mid.val){
                return false;
            }
            head = head.next;
            mid = mid.next;
        }
        return true;


    }
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next !=null && fast.next.next  != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curN = head.next;
        head.next = null;
        while(curN != null) {
            cur = curN;
            curN = curN.next;
            cur.next = head;
            head = cur;
        }
        return head;
    }
}
